package primary.dynamic_programming;

import java.util.Arrays;
import java.util.Optional;
import java.util.function.BinaryOperator;

/**
 * @Author Elephas
 * @Date 2022/1/9
 **/
public class MaxSubArray {
    public static void main(String[] args) {
        final int[] TEST_01 = new int[]{-1,-2};
        new MaxSubArray().maxSubArray2(TEST_01);
    }

    public int maxSubArray(int[] sums){
        if(sums.length == 0)
            return 0;
        int sum=0,maxSum=0;
        for (int i = 0; i < sums.length; i++) {
            sum += sums[i];
            if(sum > maxSum)
                maxSum = sum;
            if(sum < 0)
                sum = 0;
        }
        
        // 特殊情况，数组内所有元素均为负数，寻找最大的负数。
        if( maxSum == 0){
            maxSum = sums[0];
            for (int i = 1; i < sums.length; i++) {
                if( sums[i] > maxSum)
                    maxSum = sums[i];
            }
        }
        return maxSum;
    }

    /*
        解法二:分治法，将数组二分，最大子数组要么在左边，要么在右边，要么横跨中点,时间复杂度o(nlogn),由于使用了递归栈，所以空间复杂度为o(logn)
     */
    public int maxSubArray2(int[] sums){
        return maxSubArray2Helper(sums,0,sums.length-1);
    }
    public int maxSubArray2Helper(int[] nums, int low, int high){
        if(low == high){
            return nums[low];
        }
        int mid = low + (high - low) / 2;
        int leftMax = maxSubArray2Helper(nums,low,mid);
        int rightMax = maxSubArray2Helper(nums,mid+1,high);
        int crossMax = findCrossMaxSubArray(nums,mid,low,high);
        return Arrays.asList(leftMax,rightMax,crossMax).stream().reduce(BinaryOperator.maxBy(Integer::compareTo)).orElseGet(()-> {
            return leftMax;
        });
    }
    public int findCrossMaxSubArray(int[] nums,int mid,int low,int high){
        int sum = 0;
        int maxLeftSum = Integer.MIN_VALUE, maxRightSum = Integer.MIN_VALUE;
        for (int i = mid; i >= low; i--) {
            sum+= nums[i];
            if(maxLeftSum < sum) {
                maxLeftSum = sum;
            }
        }
        sum = 0;
        for (int i = mid+1; i <= high; i++) {
            sum+= nums[i];
            if(maxRightSum < sum){
                maxRightSum = sum;
            }
        }
        return maxLeftSum + maxRightSum;
    }

}
